OI代码模板计划 - 后缀数组

代码：后缀排序

读入一个长度为 $n$ 的由小写英文字母组成的字符串，请把这个字符串的所有非空后缀按字典序从小到大排序，然后按顺序输出后缀的第一个字符在原串中的位置。位置编号为 $1$ 到 $n$。

除此之外为了进一步证明你确实有给后缀排序的超能力，请另外输出 $n−1$ 个整数分别表示排序后相邻后缀的最长公共前缀的长度。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <string>
#define MAXN 1000000 + 10
using namespace std;
char s[MAXN];
int y[MAXN], x[MAXN], c[MAXN], sa[MAXN], h[MAXN], rk[MAXN];
int N, M;
inline void print(int x)
{
    if(x < 0)
    {
        putchar('-');
        x = -x;
    }
    if(x>9)
        print(x / 10);
    putchar(x % 10 + '0');
}
inline void getsa()
{
	for (int i = 1; i <= N; ++i)
	{
		++c[x[i] = s[i]];
	}
	for (int i = 2; i <= M; ++i)
		c[i] += c[i - 1];
	for (int i = N; i > 0; --i)
	{
		sa[c[x[i]]--] = i;
	}
	for (int k = 1; k <= N; k <<= 1)
	{
		int num = 0;
		for (int i = N - k + 1; i <= N; ++i)
			y[++num] = i;
		for (int i = 1; i <= N; ++i)
			if (sa[i] > k)
				y[++num] = sa[i] - k;
		for (int i = 1; i <= M; ++i)
			c[i] = 0;
		for (int i = 1; i <= N; ++i) ++c[x[i]];
		for (int i = 2; i <= M; ++i)
			c[i] += c[i - 1];
		for (int i = N; i >= 1; i--)
			sa[c[x[y[i]]]--] = y[i], y[i] = 0;
		swap(x, y);
		x[sa[1]] = 1;num = 1;
		for (int i = 2; i <= N; ++i)
			x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] & y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++num;
		if (num == N) break;
		M = num;
	};
	for (int i = 1; i <= N; ++i)
		print(sa[i]), putchar(' '); 
}

inline void geth()
{
	int k = 0;
	for (int i = 1; i <= N; ++i)
		rk[sa[i]] = i;
	for (int i = 1; i <= N; ++i)
	{
		if (rk[i] == 1) continue;
		if (k) k--;
		int j = sa[rk[i] - 1];
		while (j + k <= N && i + k <= N && s[i + k] == s[j + k]) ++k;
		h[rk[i]] = k;
	}
	putchar(10);
	for (int i = 2; i <= N; ++i)
		print(h[i]), putchar(' '); 
}
signed main(int argc, char **Argv)
{
	gets(s+1);
    N = strlen(s+1);
    M = 122;
    getsa();
    geth();
	return 0;
}